import java.util.*;

/**
 * @author 03010570
 * @date 2020/07/17
 * describe:    LeetCode : 51、N皇后
 */
public class LeetCode_51 {

    public static void main(String[] args) {
        LeetCode_51 code51 = new LeetCode_51();
        List<List<String>> queens = code51.solveNQueens(8);
        int index = 0;
        for (List<String> queen : queens) {
            System.out.println(++index);
            for (String s : queen) {
                System.out.println(s);
            }
            System.out.println();
        }

    }


    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<>();
        Set<Integer> leftDowns = new HashSet<>();
        Set<Integer> rightDowns = new HashSet<>();
        backtrack(solutions, queens, n, 0, columns, leftDowns, rightDowns);
        return solutions;
    }

    private void backtrack(List<List<String>> solutions, int[] queens, int n,
                           int curRow, Set<Integer> columns, Set<Integer> leftDowns, Set<Integer> rightDowns) {
        if (curRow == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            for (int i = 0; i < n; i++) { // 循环列
                // 判断列是否包含 i
                if (columns.contains(i)) {
                    continue;
                }
                // 左下的同一根斜线 满足 当前行 - 当前列 = 等于同一个 值
                // 假如说 添加了 0，则 所有的 （1，1）（2，2）（3，3） 的左下斜线都包含，则直接跳过
                // 判断 左下斜线 是否包含 当前 行 - 当前列
                int leftDown = curRow - i;
                if (leftDowns.contains(leftDown)) {
                    continue;
                }
                // 右下斜线同理，满足条件有所不同， 当前行 + 当前列 等于 同一个值
                int rightDown = curRow + i;
                if (rightDowns.contains(rightDown)) {
                    continue;
                }
                // 说明当前行 的 当前列 满足条件，可以放置 皇后，queen
                queens[curRow] = i;
                // 放了皇后之后 要做的事，当前列 不能再放皇后，当前 左下斜线 和当前右下斜线也不能放皇后
                columns.add(i);
                leftDowns.add(leftDown);
                rightDowns.add(rightDown);
                // 回溯,下一行
                backtrack(solutions, queens, n, curRow + 1, columns, leftDowns, rightDowns);
                // 恢复
                queens[curRow] = -1;
                columns.remove(i);
                leftDowns.remove(leftDown);
                rightDowns.remove(rightDown);
            }
        }
    }

    private List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] rows = new char[n];
            Arrays.fill(rows, '.');
            rows[queens[i]] = 'Q';
            board.add(new String(rows));
        }
        return board;

    }
}
